// LeetCode 主站 Problem Nr. 401: 二进制手表

/*
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。
你可以 按任意顺序 返回答案。

小时不会以零开头：
    例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
分钟必须由两位数组成，可能会以零开头：
    例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例 1：
	输入：turnedOn = 1
	输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
示例 2：
	输入：turnedOn = 9
	输出：[]

提示：
    0 <= turnedOn <= 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-watch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"
	"math/bits"
)

func readBinaryWatch(turnedOn int) []string {
	if turnedOn == 0 {
		return []string{"0:00"}
	}
	return method1(turnedOn)
}

func method1(turnedOn int) []string {
	result := make([]string, 0)
	used := 0
	combine := make([]byte, 10)

	var backtracking func(index int)
	backtracking = func(index int) {
		if index < len(combine) {
			combine[index] = '1' - '0'
			used++
		
			
			if used == turnedOn {
				if time, ok := checkCombine(combine); ok {
					result = append(result, time)
				}
			}

			backtracking(index+1)

			combine[index] = '0' - '0'
			used--
			backtracking(index+1)
		}
	}

	backtracking(0)
	return result
}

func binaryToDecimal(bits []byte) int {
	var result int = 0
	for _, b := range bits {
		result = 2 * result + int(b)
	}
	return result
}

func checkCombine(combine []byte) (string, bool) {
	hour, minute := binaryToDecimal(combine[:4]), binaryToDecimal(combine[4:])
	if 0 <= hour && hour < 12 && 0 <= minute && minute < 60 {
		return fmt.Sprintf("%d:%.2d", hour, minute), true
	}
	return "", false
}

func method2(turnedOn int) (result []string) {
	for h := uint8(0); h < 12; h++ {
        for m := uint8(0); m < 60; m++ {
            if bits.OnesCount8(h)+bits.OnesCount8(m) == turnedOn {
                result = append(result, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return
}

func method3(turnedOn int) (result []string) {
	for i := 0; i < 1024; i++ {
        h, m := i>>6, i&63 // 用位运算取出高 4 位和低 6 位
        if h < 12 && m < 60 && bits.OnesCount(uint(i)) == turnedOn {
            result = append(result, fmt.Sprintf("%d:%02d", h, m))
        }
    }
    return
}

func main() {
	fmt.Println(readBinaryWatch(8))
}
